package swardToOffer.method_4_dp_or_greedy;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * @Author ChanZany
 * @Date 2021/5/25 14:41
 * @Version 1.0
 * 面试题49：丑数
 * 题目：我们把只包含因子2、3和5的数称作丑数（Ugly Number）。求按从小到
 * 大的顺序的第1500个丑数。例如6、8都是丑数，但14不是，因为它包含因子7。
 * 习惯上我们把1当做第一个丑数。
 *  方法一:最小堆:
 *  要得到从小到大的第 nn 个丑数，可以使用最小堆实现。
 * 初始时堆为空。首先将最小的丑数 1加入堆。每次取出堆顶元素x,则x是堆中最小的丑数，由于2x,3x,5x也是丑数,因此将之加入堆
 * 上述做法会导致堆中出现重复元素的情况。为了避免重复元素，可以使用哈希集合去重，避免相同元素多次加入堆。
 * 在排除重复元素的情况下，第 n 次从最小堆中取出的元素即为第 n 个丑数
 *
 * 方法二：动态规划
 * 丑数的递推性质： 丑数只包含因子 2, 3, 5 ，因此有 “丑数 == 某较小丑数×某因子” （例如：10=5×2 9=3x3,12=3x4=2x6）。
 * 设已知长度为n的丑数序列x1...xn,求第n+1个丑数xn+1,基于递推性质,可以得到
 * xn+1 = xa * 2, a,b,c in 1~n
 * = xb * 3
 * = xc * 5
 * 若索引a,b,c满足以上条件.则下一个丑数为 xn+1= min{xa*2,xb*3,xc*5}
 * 由于 x_{n+1}是最接近 x_n的丑数，因此索引 a, b, c需满足以下条件：
 * 条件1:
 * x_a*2 > x_n >= x_{a-1}*2
 * x_b*3> x_n >= x_{b-1}*3
 * x_c*5> x_n >= x+{c-1}*5
 * 以丑数序列1,2,3,4,5,6为例, 现在求下一个丑数,则a,b,c的选择过程如下
 * 6<5x2 而 6 < 4*2,所以a不能是5
 * 6<4x2 且 6 >= 3x2 ,所以 a可以是4
 * 6<3x3 且 6 >= 2x3,所以b可以是3
 * 6<2x5 且 6 >= 1x5,所以c可以是2
 * 可以看到a,b,c满足 a>b>c
 *
 * 动态规划解析:
 * 状态定义: dp[i]代表第i个丑数
 * 转移方程: dp[i] = min{dp[a]*2,dp[b]*3,dp[c]*5},a>b>c且满足条件1
 * 初始状态: dp[1]=1,即第一个丑数为1;
 * 返回值:dp[n]
 */
public class UglyNumber {
    public int nthUglyNumber2(int n) {
        int[] factors = {2, 3, 5};
        Set<Long> seen = new HashSet<Long>();
        PriorityQueue<Long> heap = new PriorityQueue<Long>();
        seen.add(1L);
        heap.offer(1L);
        int ugly = 0;
        for (int i = 0; i < n; i++) {
            long curr = heap.poll();
            ugly = (int) curr;
            for (int factor : factors) {
                long next = curr * factor;
                if (seen.add(next)) {
                    heap.offer(next);
                }
            }
        }
        return ugly;
    }


    public int nthUglyNumber(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        int a=1,b=1,c=1;
        for (int i = 1; i <n; i++) {
            int n2 = dp[a]*2,n3=dp[b]*3,n5=dp[c]*5;
            //新的丑数必定是dp[a]/dp[b]/dp[c]的倍数
            dp[i+1] = Math.min(Math.min(n2,n3),n5);
            //下一次循环中满足dp[i]<=min(n2,n3,n5)
            if (dp[i+1]==n2) a++;
            if (dp[i+1]==n3) b++;
            if (dp[i+1]==n5) c++;
        }
        return dp[n];
    }

    public static void main(String[] args) {
        UglyNumber Main = new UglyNumber();
        System.out.println(Main.nthUglyNumber(7));
    }
}
